{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第2章感知机-习题\n",
    "\n",
    "### 习题2.1\n",
    "&emsp;&emsp;Minsky 与 Papert 指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或 (XOR)。验证感知机为什么不能表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "\n",
    "对于异或函数XOR，全部的输入与对应的输出如下：  \n",
    "\n",
    "|<div style=\"width:20px\">$x^{(1)}$</div>|<div style=\"width:20px\">$x^{(2)}$</div>|$y$|\n",
    "|:-: | :-: | :-: |  \n",
    "| &nbsp;1 |  &nbsp;1 |-1 | \n",
    "| &nbsp;1 | -1 | &nbsp;1 | \n",
    "|-1 |  &nbsp;1 | &nbsp;1 | \n",
    "|-1 | -1 |-1 | "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>x1</th>\n",
       "      <th>x2</th>\n",
       "      <th>y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>-1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>-1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>-1</td>\n",
       "      <td>-1</td>\n",
       "      <td>-1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   x1  x2  y\n",
       "0   1   1 -1\n",
       "1   1  -1  1\n",
       "2  -1   1  1\n",
       "3  -1  -1 -1"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "x1 = [1, 1, -1, -1]\n",
    "x2 = [1, -1, 1, -1]\n",
    "y = [-1, 1, 1, -1]\n",
    "x1 = np.array(x1)\n",
    "x2 = np.array(x2)\n",
    "y = np.array(y)\n",
    "data = np.c_[x1, x2, y]\n",
    "data = pd.DataFrame(data, index=None, columns=['x1', 'x2', 'y'])\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEKCAYAAAASByJ7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAMcElEQVR4nO3df6jd913H8ecrzUabdiKyC64/0htkrNYyHDt3Uypztw7MhlhXsrBSqrjKhavDCQqbjiC25g8z6D86rlzoKMzr5iVdsXTTusnVYKfznpQqiVm1LG0XUl2GDANVZ+jbP84n7b1pcu/Nzbn3e0/u8wHh3vM933O+bw7Jfeb7/Z7zvakqJEna0fUAkqStwSBIkgCDIElqDIIkCTAIkqTGIEiSgA6DkOSWJAtJTiQ5nuQTXc0iSYJ09TmEJG8D3lZVzyR5C3AU+IWq+pdOBpKkba6zPYSqermqnmnfnwVOADd1NY8kbXc7ux4AIMk48C7gGxe5bwqYArj++uvffdttt23ucJI04o4ePfrdqhpbbb3ODhm9NkByA/C3wMGq+tJK6/Z6ver3+5szmCRdJZIcrareaut1+i6jJG8CHgPmVouBJGljdfkuowCPACeq6uGu5pAkDXS5h3AncD9wV5Jn258PdTiPJG1rnZ1Urqq/A9LV9iVJy/lJZUkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJElNp0FI8rkk30lyrMs5tp25ORgfhx07Bl/n5rqeSOLQ04dYOLmwbNnCyQUOPX2oo4m2n673EB4F9nY8w/YyNwdTU/Dii1A1+Do1ZRTUuYkbJ9h/eP9rUVg4ucD+w/uZuHGi48m2j1RVtwMk48CTVXXHauv2er3q9/sbP9TVbHx8EIEL3XorvPDCZk8jLXM+AtO9aWb6M8zvm2dyz2TXY428JEerqrfael3vIawqyVSSfpL+mTNnuh5n9L300uUtlzbR5J5JpnvTPHTkIaZ708Zgk235IFTVbFX1qqo3NjbW9Tijb/fuy1subaKFkwvM9Gc48L4DzPRn3nBOQRtrywdBQ3bwIOzatXzZrl2D5VKHzh8umt83z4OTDzK/b37ZOQVtPIOw3dx3H8zODs4ZJIOvs7OD5VKHFk8vLjtnMLlnkvl98yyeXux4su2j05PKSb4AvB94K/AfwO9W1SOXWt+TypJ0+dZ6UnnnZgxzKVV1b5fblyS9zkNGkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkYJUgJPmBJD9ykeXvHMbGk+xN8lyS55N8ahjPKUlan0sGIcl+4JvAY0mOJ5lYcvejV7rhJNcAnwU+CNwO3Jvk9it9XknS+qy0h/A7wLur6seBXwY+n+Sedl+GsO33AM9X1beq6vvAF4G7h/C8kqR12LnCfddU1csAVfWPSSaBJ5PcDNQQtn0T8O0lt08B771wpSRTwBTA7t27h7BZSdLFrLSHcHbp+YMWh/cz+F/8jw1h2xfby3hDaKpqtqp6VdUbGxsbwmYlSRezUhCmgR1Lj+tX1VlgL/ArQ9j2KeCWJbdvBk4P4XklSetwySBU1T9V1b8B80k+mYHrgIeBXx3CtheBtyfZk+TNwEeBJ4bwvJKkdVjL5xDey+B/8l9n8EP8NHDnlW64qs4BHweeAk4A81V1/EqfV5K0PiudVD7v/4D/Bq4DrgVOVtWrw9h4VX0F+MownkuSdGXWsoewyCAIE8BPMfi8wOENnUqStOnWsofwQFX12/f/Dtyd5P4NnEmS1IFV9xCWxGDpss9vzDiSpK54cTtJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSY1BkCQBBkGS1BgESRJgECRJjUGQJAEGQZLUGARJEmAQJEmNQZAkAQZBktQYBEkSYBAkSU0nQUjykSTHk7yapNfFDNvVoacPsXByYdmyhZMLHHr6UEcTSUvMzcH4OOzYMfg6N9f1RNtKV3sIx4B7gCMdbX/bmrhxgv2H978WhYWTC+w/vJ+JGyc6nkzb3twcTE3Biy9C1eDr1JRR2ESpqu42nvwN8FtV1V/L+r1er/r9Na2qFZyPwHRvmpn+DPP75pncM9n1WNruxscHEbjQrbfCCy9s9jRXlSRHq2rVozFb/hxCkqkk/ST9M2fOdD3OVWFyzyTTvWkeOvIQ071pY6Ct4aWXLm+5hm7DgpDka0mOXeTP3ZfzPFU1W1W9quqNjY1t1LjbysLJBWb6Mxx43wFm+jNvOKcgdWL37stbrqHbuVFPXFUf2Kjn1vqdP1x0/jDR5PjksttSZw4eHJwzeOWV15ft2jVYrk2x5Q8ZabgWTy8u++E/uWeS+X3zLJ5e7HgybXv33Qezs4NzBsng6+zsYLk2RScnlZN8GPhDYAz4HvBsVf3sao/zpLIkXb61nlTesENGK6mqx4HHu9i2JOniPGQkSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJIagyBJAgyCJKkxCJIkwCBIkhqDIEkCDIIkqekkCEk+k+SbSf45yeNJfrCLOSRJr+tqD+GrwB1V9U7gX4Hf7mgOSVLTSRCq6q+q6ly7+Q/AzV3MIUl63c6uBwA+BvzZpe5MMgVMtZv/m+TYpky1PbwV+G7XQ1wlfC2Hy9dzuN6xlpVSVRuy9SRfA374Ind9uqr+vK3zaaAH3FNrGCRJv6p6w510+/L1HB5fy+Hy9Ryutb6eG7aHUFUfWOn+JL8E/BzwM2uJgSRpY3VyyCjJXuCTwE9X1StdzCBJWq6rdxn9EfAW4KtJnk3yx2t83OwGzrQd+XoOj6/lcPl6DteaXs8NO4cgSRotflJZkgQYBElSM3JB8LIXw5PkI0mOJ3k1iW/xW6cke5M8l+T5JJ/qep5RluRzSb7j542uXJJbkiwkOdH+nX9itceMXBDwshfDdAy4BzjS9SCjKsk1wGeBDwK3A/cmub3bqUbao8Deroe4SpwDfrOqfhT4CeDXVvu7OXJB8LIXw1NVJ6rqua7nGHHvAZ6vqm9V1feBLwJ3dzzTyKqqI8B/dj3H1aCqXq6qZ9r3Z4ETwE0rPWbkgnCBjwF/0fUQ2tZuAr695PYpVvlHJ222JOPAu4BvrLTeVriW0RtcxmUvzgFzmznbqFnLa6krkoss873c2jKS3AA8BvxGVf3XSutuySB42YvhWe211BU7Bdyy5PbNwOmOZpGWSfImBjGYq6ovrbb+yB0yWnLZi5/3shfaAhaBtyfZk+TNwEeBJzqeSSJJgEeAE1X18FoeM3JBYP2XvdAFknw4ySngJ4EvJ3mq65lGTXuDw8eBpxictJuvquPdTjW6knwB+HvgHUlOJXmg65lG2J3A/cBd7Wfls0k+tNIDvHSFJAkYzT0ESdIGMAiSJMAgSJIagyBJAgyCJKkxCNKQJPnLJN9L8mTXs0jrYRCk4fkMg/d9SyPJIEiXKclE+30c1ya5vl1r/o6q+mvgbNfzSeu1Ja9lJG1lVbWY5Ang94HrgD+pKn+hi0aeQZDW50EG1zH6H+DXO55FGgoPGUnr80PADQyuq3Vtx7NIQ2EQpPWZBQ4w+H0cf9DxLNJQeMhIukxJfhE4V1V/2n6n8teT3AX8HnAbcEO7iuwDVeUVZDUyvNqpJAnwkJEkqTEIkiTAIEiSGoMgSQIMgiSpMQiSJMAgSJKa/wc0vPMhJXGnfAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "positive = data.loc[data['y'] == 1]\n",
    "negative = data.loc[data['y'] == -1]\n",
    "\n",
    "plt.xlim(-2, 2)\n",
    "plt.ylim(-2, 2)\n",
    "plt.xticks([-2, -1, 0, 1, 2])\n",
    "plt.yticks([-2, -1, 0, 1, 2])\n",
    "plt.xlabel(\"x1\")\n",
    "plt.ylabel(\"x2\")\n",
    "plt.plot(positive['x1'], positive['x2'], \"ro\")\n",
    "plt.plot(negative['x1'], negative['x2'], \"gx\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "显然感知机无法使用一条直线将两类样本划分，异或问题是线性不可分的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题2.2\n",
    "\n",
    "&emsp;&emsp;模仿例题 2.1，构建从训练数据求解感知机模型的例子。\n",
    "\n",
    "**解答：**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w: [[1. 0.]] \n",
      "b: [-2.] \n",
      "\n",
      "[ 1  1 -1]\n"
     ]
    }
   ],
   "source": [
    "from sklearn.linear_model import Perceptron\n",
    "import numpy as np\n",
    "\n",
    "X_train = np.array([[3, 3], [4, 3], [1, 1]])\n",
    "y = np.array([1, 1, -1])\n",
    "\n",
    "perceptron_model = Perceptron()\n",
    "perceptron_model.fit(X_train, y)\n",
    "print(\"w:\", perceptron_model.coef_, \"\\nb:\", perceptron_model.intercept_, \"\\n\")\n",
    "\n",
    "result = perceptron_model.predict(X_train)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题2.3\n",
    "证明以下定理：样本集线性可分的充分必要条件是正实例点所构成的凸壳与负实例点所构成的凸壳互不相交。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**  \n",
    "**第1步：**首先给出凸壳与线性可分的定义，定义如下：  \n",
    "**凸壳**  \n",
    "**定义1：**设集合$S \\subset R^n$，是由$R^n$中的$k$个点所组成的集合，即$S=\\{x_1,x_2,\\cdots, x_k\\}$。定义$S$的凸壳$\\text{conv}(S)$为：$$\\text{conv}(S) = \\left\\{ x = \\sum_{i=1}^k \\lambda_i x_i \\Big| \\sum_{i=1}^k \\lambda_i=1,\\lambda_i \\geqslant 0, i=1,2,\\cdots, k \\right\\}$$说明：凸壳是一个集合，对于所有可能的$\\lambda_i,i=1,2,\\cdots,k$只要满足$\\displaystyle \\sum_{i=1}^k \\lambda_i = 1$，那么$\\displaystyle x = \\sum_{i=1}^k$即为凸壳中的元素，凸壳可以用二维的图形表示如下：\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);width:470.17px;\" src=\"../images/2-1-Convex-Hull.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图2.1 凸壳</div></center>\n",
    "\n",
    "**线性可分**  \n",
    "**定义2：**给定一个数据集$$T=\\{(x_1,y_1), (x_2,y_2), \\cdots, (x_n,y_n)\\}$$其中$x_i \\in \\mathcal{X}=R_n, y_i \\in \\mathcal{Y} = \\{+1, -1\\}, i=1,2,\\cdots, n$，如果存在某个超平面$S：w \\cdot x + b = 0$，能够将数据集的正实例点和负实例点完全正确划分到超平面的两侧，即对所有的正实例点即$y_i=+1$的实例$i$，有$w \\cdot x_i + b > 0$，对所有的负实例点即$y_i = -1$的实例$i$，有$w \\cdot x_i + b < 0$，则称数据集$T$线性可分，否则称数据集$T$线性不可分。  \n",
    "\n",
    "----\n",
    "\n",
    "**第2步：** 证明必要性：线性可分$\\Rightarrow$凸壳不相交  \n",
    "假设数据集$T$中的正例点集为$S_+$，$S_+$的凸壳为$\\text{conv}(S_+)$，负实例点集为$S_-$，$S_-$的凸壳为$\\text{conv}(S_-)$，若$T$是线性可分的，则存在一个超平面：$$w \\cdot x + b = 0$$能够将$S_+$和$S_-$完全分离。假设对于所有的正例点$x_i$，有：$$w \\cdot x_i + b = \\varepsilon_i$$易知$\\varepsilon_i > 0, i = 1,2,\\cdots,|S_+|。$若$\\text{conv}(S_+)$和$\\text{conv}(S_-)$相交，即存在某个元素$s$，同时满足$s \\in \\text{conv}(S_+)$和$s \\in \\text{conv}(S_-)$。  \n",
    "对于$\\text{conv}(S_+)$中的元素$s^+$有$$w \\cdot s^+ = w \\cdot \\sum_{i=1}^k \\lambda_i x_i = \\sum_{i=1}^k \\lambda_i(\\varepsilon_i - b) = \\sum_{i=1}^k \\lambda_i \\varepsilon_i - b $$因此$\\displaystyle w \\cdot s^+ + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i > 0$，同理对于$S_-$中的元素$s^-$有$\\displaystyle w \\cdot s^- + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i < 0$  \n",
    "由于$s \\in \\text{conv}(S_+)$且$s \\in \\text{conv}(S_-)$，则$\\displaystyle w \\cdot s + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i > 0$且$\\displaystyle w \\cdot s + b = \\sum_{i=1}^k \\lambda_i \\varepsilon_i < 0$，可推出矛盾。  \n",
    "因此，$\\text{conv}(S_+)$ 和$\\text{conv}(S_-)$必不相交。从而必要性得证。  \n",
    "\n",
    "----\n",
    "\n",
    "**第3步：**  \n",
    "证明充分性：凸壳不相交$\\Rightarrow$线性可分  \n",
    "假设数据集$T$中的正例点集为$S_+$，$S_+$的凸壳为$\\text{conv}(S_+)$，负实例点集为$S_-$，$S_-$的凸壳为$\\text{conv}(S_-)$，且$\\text{conv}(S_+)$与$\\text{conv}(S_-)$不相交。  \n",
    "定义两个点$x_1,x_2$的距离为$$\\text{dist}(x_1,x_2) = \\|x_1 - x_2\\|_2 = \\sqrt{(x_1 - x_2)^2}$$  \n",
    "定义$\\text{conv}(S_+)$和$\\text{conv}(S_-)$距离为$$\\text{dist}(\\text{conv}(S_+),\\text{conv}(S_-)) = \\min \\|s_+ - s_-\\|, s_+ \\in \\text{conv}(S_+), s_- \\in \\text{conv}(S_-)$$  \n",
    "设$x_+ \\in \\text{conv}(S_+), x_- \\in \\text{conv}(S_-)$且$\\text{dist}(x_+, x_-) = \\text{dist}(\\text{conv}(S_+),\\text{conv}(S_-))$。则对于任意正例点$x$有$\\text{dist}(x,x_-) \\geqslant \\text{dist}(x_+ , x_-)$。同理，对弈所有的负例点$x$有$\\text{dist}(x,x_+) \\geqslant \\text{dist}(x , x_-)$。  \n",
    "存在超平面$$w \\cdot x + b = 0$$其中$$w = x_+ - x_- \\\\ b = -\\frac{x_+ \\cdot x_+ -  x_- \\cdot x_-}{2}$$  \n",
    "则对于所有的正例点$x$（易知$x \\cdot x_+ + b > 0$，因此若$x_+$属于正例点，则令$x_+ \\neq x$）$$\\begin{aligned}\n",
    "w\\cdot x +b \n",
    "& = (x_+-x_-)\\cdot x-\\frac{x_+ \\cdot x_+ - x_- \\cdot x_-}{2} \\\\\n",
    "& = x_+ \\cdot x -x_- \\cdot x - \\frac{x_+ \\cdot x_+ -x_- \\cdot x_-}{2} \\\\\n",
    "& = \\frac{||x_- - x||_2^2-||x_+ - x||_2^2}{2}\\\\\n",
    "& = \\frac{\\text{dist}(x,x_-)^2-\\text{dist}(x,x_+)^2}{2}\n",
    "\\end{aligned}$$若$\\text{dist}(x,x_-) \\leqslant \\text{dist}(x,x_+)$（即线性不可分），则$\\text{dist}(x,x_-) \\leqslant \\text{dist}(x,x_+) \\leqslant \\text{dist}(x_-,x_+)$，那么$\\text{dist}(\\text{conv}(S_+),\\text{conv}(S_-)) < \\text{dist}(x_+,x_-)$，推出矛盾，因此$\\text{dist}(x,x_-) > \\text{dist}(x,x_+)$，即线性可分，充分性得证。  \n",
    "\n",
    "----\n",
    "\n",
    "**补充：**用反证法证明$\\text{dist}(x,x_-) > \\text{dist}(x,x_+)$  \n",
    "**证明：**假设$\\text{dist}(x,x_-) \\leqslant \\text{dist}(x,x_+)$则存在$$t=\\frac{(x_{-}-x_{+})\\cdot (x-x_{+})}{||x-x_{+}||_2^2}$$令$x' = tx + (1-t) x _+$，则$(x_- - x') \\cdot (x_+ - x) = 0$  \n",
    "易知$t \\leqslant 1$，先证明$t > 0$：  \n",
    "可以将$x, x_+, x_-$看做为空间中的三个不同的点，三条边的长度分别为$\\text{dist}(x, x_+)，\\text{dist}(x, x_-)，\\text{dist}(x_+, x_-)$  \n",
    "如上面可知$\\text{dist}(x,x_+) \\geqslant \\text{dist}(x,x_-) \\geqslant \\text{dist}(x_-,x_+)$  \n",
    "根据三角形的大边对应大角这一特性，很容易可以看出$x_+-x$与$x_+ - x_-$之间的夹角小于90度，因此$t > 0$。  \n",
    "那么$\\text{dist}(x',x_-) < \\text{dist}(x_+,x_-)$，又因为$x'$必在$\\text{conv}(S_+)$内部，故推出矛盾，所以$\\text{dist}(x,x_-) > \\text{dist}(x,x_+)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
